/* --mode:java; c-basic-offset:2; -- */
/*
 * Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved. Redistribution and use in source and binary
 * forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions
 * of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2.
 * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following
 * disclaimer in the documentation and/or other materials provided with the distribution. 3. The names of the authors
 * may not be used to endorse or promote products derived from this software without specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
 * INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
/*
 * This program is based on zlib-1.1.3, so all credit should go authors Jean-loup Gailly(jloup@gzip.org) and Mark
 * Adler(madler@alumni.caltech.edu) and contributors of zlib.
 */

package net.sf.javadc.util.zlib;

final class Tree
{
    static final private int MAX_BITS      = 15;

    static final private int BL_CODES      = 19;

    static final private int D_CODES       = 30;

    static final private int LITERALS      = 256;

    static final private int LENGTH_CODES  = 29;

    static final private int L_CODES       = LITERALS + 1 + LENGTH_CODES;

    static final private int HEAP_SIZE     = 2 * L_CODES + 1;

    // Bit length codes must not exceed MAX_BL_BITS bits
    static final int         MAX_BL_BITS   = 7;

    // end of block literal code
    static final int         END_BLOCK     = 256;

    // repeat previous bit length 3-6 times (2 bits of repeat count)
    static final int         REP_3_6       = 16;

    // repeat a zero length 3-10 times (3 bits of repeat count)
    static final int         REPZ_3_10     = 17;

    // repeat a zero length 11-138 times (7 bits of repeat count)
    static final int         REPZ_11_138   = 18;

    // extra bits for each length code
    static final int[]       extra_lbits   =
                                               { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4,
                    4, 5, 5, 5, 5, 0          };

    // extra bits for each distance code
    static final int[]       extra_dbits   =
                                               { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10,
                    10, 11, 11, 12, 12, 13, 13 };

    // extra bits for each bit length code
    static final int[]       extra_blbits  = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7 };

    static final byte[]      bl_order      = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };

    // The lengths of the bit length codes are sent in order of decreasing
    // probability, to avoid transmitting the lengths for unused bit
    // length codes.

    static final int         Buf_size      = 8 * 2;

    // see definition of array dist_code below
    static final int         DIST_CODE_LEN = 512;

    static final byte[]      _dist_code    =
                                               { 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8,
                    8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11,
                    11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
                    12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13,
                    13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
                    13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
                    14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
                    14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15,
                    15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
                    15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
                    15, 15, 15, 15, 15, 15, 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22,
                    22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
                    24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26,
                    26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
                    26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
                    27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
                    28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
                    28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29,
                    29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
                    29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
                    29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29 };

    static final byte[]      _length_code  =
                                               { 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12,
                    13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17,
                    17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20,
                    20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
                    21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
                    23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
                    24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
                    25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26,
                    26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
                    26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
                    27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28 };

    static final int[]       base_length   =
                                               { 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
                    64, 80, 96, 112, 128, 160, 192, 224, 0 };

    static final int[]       base_dist     =
                                               { 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384,
                    512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576 };

    short[]                  dyn_tree;                                                                            // the
                                                                                                                   // dynamic
                                                                                                                   // tree

    int                      max_code;                                                                            // largest
                                                                                                                   // code
                                                                                                                   // with
                                                                                                                   // non
                                                                                                                   // zero
                                                                                                                   // frequency

    StaticTree               stat_desc;                                                                           // the
                                                                                                                   // corresponding
                                                                                                                   // static
                                                                                                                   // tree

    // Reverse the first len bits of a code, using straightforward code (a
    // faster
    // method would use a table)
    // IN assertion: 1 <= len <= 15
    static int bi_reverse(
        int code, // the value to invert
        int len // its bit length
    )
    {
        int res = 0;
        do
        {
            res |= code & 1;
            code >>>= 1;
            res <<= 1;
        }
        while ( --len > 0 );
        return res >>> 1;
    }

    // Mapping from a distance to a distance code. dist is the distance - 1 and
    // must not have side effects. _dist_code[256] and _dist_code[257] are never
    // used.
    static int d_code(
        int dist )
    {
        return dist < 256 ? _dist_code[dist] : _dist_code[256 + (dist >>> 7)];
    }

    // Generate the codes for a given tree and bit counts (which need not be
    // optimal).
    // IN assertion: the array bl_count contains the bit length statistics for
    // the given tree and the field len is set for all tree elements.
    // OUT assertion: the field code is set for all tree elements of non
    // zero code length.
    static void gen_codes(
        short[] tree, // the tree to decorate
        int max_code, // largest code with non zero frequency
        short[] bl_count // number of codes at each bit length
    )
    {
        short[] next_code = new short[MAX_BITS + 1]; // next code value for
        // each bit length
        short code = 0; // running code value
        int bits; // bit index
        int n; // code index

        // The distribution counts are first used to generate the code values
        // without bit reversal.
        for ( bits = 1; bits <= MAX_BITS; bits++ )
        {
            next_code[bits] = code = (short) (code + bl_count[bits - 1] << 1);
        }

        // Check that the bit counts in bl_count are consistent. The last code
        // must be all ones.
        // Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
        // "inconsistent bit counts");
        // Tracev((stderr,"\ngen_codes: max_code %d ", max_code));

        for ( n = 0; n <= max_code; n++ )
        {
            int len = tree[n * 2 + 1];
            if ( len == 0 )
            {
                continue;
            }
            // Now reverse the bits
            tree[n * 2] = (short) bi_reverse( next_code[len]++, len );
        }
    }

    // Construct one Huffman tree and assigns the code bit strings and lengths.
    // Update the total bit length for the current block.
    // IN assertion: the field freq is set for all tree elements.
    // OUT assertions: the fields len and code are set to the optimal bit length
    // and corresponding code. The length opt_len is updated; static_len is
    // also updated if stree is not null. The field max_code is set.
    void build_tree(
        Deflate s )
    {
        short[] tree = dyn_tree;
        short[] stree = stat_desc.static_tree;
        int elems = stat_desc.elems;
        int n, m; // iterate over heap elements
        int max_code = -1; // largest code with non zero frequency
        int node; // new node being created

        // Construct the initial heap, with least frequent element in
        // heap[1]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
        // heap[0] is not used.
        s.heap_len = 0;
        s.heap_max = HEAP_SIZE;

        for ( n = 0; n < elems; n++ )
        {
            if ( tree[n * 2] != 0 )
            {
                s.heap[++s.heap_len] = max_code = n;
                s.depth[n] = 0;
            }
            else
            {
                tree[n * 2 + 1] = 0;
            }
        }

        // The pkzip format requires that at least one distance code exists,
        // and that at least one bit should be sent even if there is only one
        // possible code. So to avoid special checks later on we force at least
        // two codes of non zero frequency.
        while ( s.heap_len < 2 )
        {
            node = s.heap[++s.heap_len] = max_code < 2 ? ++max_code : 0;
            tree[node * 2] = 1;
            s.depth[node] = 0;
            s.opt_len--;
            if ( stree != null )
            {
                s.static_len -= stree[node * 2 + 1];
                // node is 0 or 1 so it does not have extra bits
            }
        }
        this.max_code = max_code;

        // The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
        // establish sub-heaps of increasing lengths:

        for ( n = s.heap_len / 2; n >= 1; n-- )
        {
            s.pqdownheap( tree, n );
        }

        // Construct the Huffman tree by repeatedly combining the least two
        // frequent nodes.

        node = elems; // next internal node of the tree
        do
        {
            // n = node of least frequency
            n = s.heap[1];
            s.heap[1] = s.heap[s.heap_len--];
            s.pqdownheap( tree, 1 );
            m = s.heap[1]; // m = node of next least frequency

            s.heap[--s.heap_max] = n; // keep the nodes sorted by frequency
            s.heap[--s.heap_max] = m;

            // Create a new node father of n and m
            tree[node * 2] = (short) (tree[n * 2] + tree[m * 2]);
            s.depth[node] = (byte) (Math.max( s.depth[n], s.depth[m] ) + 1);
            tree[n * 2 + 1] = tree[m * 2 + 1] = (short) node;

            // and insert the new node in the heap
            s.heap[1] = node++;
            s.pqdownheap( tree, 1 );
        }
        while ( s.heap_len >= 2 );

        s.heap[--s.heap_max] = s.heap[1];

        // At this point, the fields freq and dad are set. We can now
        // generate the bit lengths.

        gen_bitlen( s );

        // The field len is now set, we can generate the bit codes
        gen_codes( tree, max_code, s.bl_count );
    }

    // Compute the optimal bit lengths for a tree and update the total bit
    // length
    // for the current block.
    // IN assertion: the fields freq and dad are set, heap[heap_max] and
    // above are the tree nodes sorted by increasing frequency.
    // OUT assertions: the field len is set to the optimal bit length, the
    // array bl_count contains the frequencies for each bit length.
    // The length opt_len is updated; static_len is also updated if stree is
    // not null.
    void gen_bitlen(
        Deflate s )
    {
        short[] tree = dyn_tree;
        short[] stree = stat_desc.static_tree;
        int[] extra = stat_desc.extra_bits;
        int base = stat_desc.extra_base;
        int max_length = stat_desc.max_length;
        int h; // heap index
        int n, m; // iterate over the tree elements
        int bits; // bit length
        int xbits; // extra bits
        short f; // frequency
        int overflow = 0; // number of elements with bit length too large

        for ( bits = 0; bits <= MAX_BITS; bits++ )
        {
            s.bl_count[bits] = 0;
        }

        // In a first pass, compute the optimal bit lengths (which may
        // overflow in the case of the bit length tree).
        tree[s.heap[s.heap_max] * 2 + 1] = 0; // root of the heap

        for ( h = s.heap_max + 1; h < HEAP_SIZE; h++ )
        {
            n = s.heap[h];
            bits = tree[tree[n * 2 + 1] * 2 + 1] + 1;
            if ( bits > max_length )
            {
                bits = max_length;
                overflow++;
            }
            tree[n * 2 + 1] = (short) bits;
            // We overwrite tree[n*2+1] which is no longer needed

            if ( n > max_code )
            {
                continue; // not a leaf node
            }

            s.bl_count[bits]++;
            xbits = 0;
            if ( n >= base )
            {
                xbits = extra[n - base];
            }
            f = tree[n * 2];
            s.opt_len += f * (bits + xbits);
            if ( stree != null )
            {
                s.static_len += f * (stree[n * 2 + 1] + xbits);
            }
        }
        if ( overflow == 0 )
        {
            return;
        }

        // This happens for example on obj2 and pic of the Calgary corpus
        // Find the first bit length which could increase:
        do
        {
            bits = max_length - 1;
            while ( s.bl_count[bits] == 0 )
            {
                bits--;
            }
            s.bl_count[bits]--; // move one leaf down the tree
            s.bl_count[bits + 1] += 2; // move one overflow item as its brother
            s.bl_count[max_length]--;
            // The brother of the overflow item also moves one step up,
            // but this does not affect bl_count[max_length]
            overflow -= 2;
        }
        while ( overflow > 0 );

        for ( bits = max_length; bits != 0; bits-- )
        {
            n = s.bl_count[bits];
            while ( n != 0 )
            {
                m = s.heap[--h];
                if ( m > max_code )
                {
                    continue;
                }
                if ( tree[m * 2 + 1] != bits )
                {
                    s.opt_len += ((long) bits - (long) tree[m * 2 + 1]) * tree[m * 2];
                    tree[m * 2 + 1] = (short) bits;
                }
                n--;
            }
        }
    }
}
